package 竞赛.NO_400;

import java.util.Arrays;
import java.util.Stack;

/**
 * 100322. 删除星号以后字典序最小的字符串
 * 创建时间： 2024-06-02 10:46
 **/
public class 删除星号以后字典序最小的字符串_100322 {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.clearStars("aaba*"));
    }

    static class Solution {
        public String clearStars(String s) {
            int n = s.length();
            boolean[] addFlag = new boolean[n];
            Stack<Integer>[] stack = new Stack[26];
            Arrays.setAll(stack, l -> new Stack<Integer>());
            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                addFlag[i] = true;
                char c = chars[i];
                if (c == '*') {
                    addFlag[i] = false;
                    for (int j = 0; j < 26; j++) {
                        if (!stack[j].isEmpty()) {
                            addFlag[stack[j].pop()] = false;
                            break;
                        }
                    }
                } else {
                    stack[c - 'a'].push(i);
                }
            }

            StringBuilder ans = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if (addFlag[i]) {
                    ans.append(chars[i]);
                }
            }
            return ans.toString();
        }
    }
}
